For today's complex mass storage systems, management of storage space allocation has become essential for efficient operation. Problems of tracking available storage space and managing allocating thereof have been recognized in the conventional art and various techniques have been developed to provide solutions. For example:
U.S. Pat. No. 8,312,242 discloses a technique of tracking memory space in a storage system. The disclosed method comprises using a hierarchical bitmap tree in a file system to represent where available and unavailable memory space exists in a storage system, the hierarchical bitmap tree having plural bitmap blocks, wherein each of at least some of the bitmap blocks is associated with summary information about bitmap blocks at a lower level in the hierarchical bitmap tree, and wherein the summary information comprises a count of free storage blocks of one or more available sizes in the memory space; and retrieving a particular bitmap block from the hierarchical bitmap tree to locate the available memory space, wherein a size of the hierarchical bitmap tree is dynamic and changes as a size of the memory space in the file system increases or decreases.
U.S. Pat. No. 8,281,103 discloses a method and apparatus for allocating storage addresses. The method includes: receiving a storage address allocation request; searching a level-2 bitmap in a hierarchical bitmap in bidirectional mode; outputting an idle bit according to the result of searching in the level-2 bitmap; obtaining a storage address according to the output idle bit, and allocating the storage address. The apparatus includes: a first receiving module, configured to receive a storage address allocation request; a first searching module, configured to search a level-2 bitmap in a hierarchical bitmap in bidirectional mode for an idle bit, wherein the hierarchical bitmap includes N level-1 bitmaps and the level-2 bitmap; and an allocating module, configured to: obtain a storage address according to the output idle bit in the level-2 bitmap, and allocate the obtained storage address.
U.S. Pat. No. 7,900,008 discloses a method and system for allocating blocks of disk in persistent storage to requesting threads. A primary data structure is provided for organizing and categorizing blocks of disk space. In addition, a secondary data structure is provided for maintaining a list of all active file system processes and blocks of disk space used by those processes. Blocks of disk space are assigned to pages. At such time as a thread may request allocation of disk space, both data structures are reviewed to determine if the requested disk space is available and to limit access of available disk space to a single page of memory to a single thread at any one time.
U.S. Pat. No. 6,874,062 discloses a system and method for locating, within a set of ordered items, N contiguous items having a desired attribute. The system utilizes a hierarchical bitmap structure. At the lowest level, a bitmap is provided, wherein each bit in the bitmap corresponds to a respective search item. The bit has a state indicative of a state of the search item. This lowest level bitmap is divided into segments. A higher-level bitmap is created, with each bit in this higher-level bitmap being associated with one of the segments and being assigned a state that describes a collective state of the search items associated with the segment. The higher-level bitmap may be sub-divided and the process repeated to create a hierarchical bitmap structure having any number of levels. The bitmap structure may be recursively searched to locate N contiguous ordered search items having a desired attribute.
U.S. Pat. No. 6,175,900 discloses a hierarchical bitmap-based memory manager that maintains a hierarchical bitmap having an entry for each memory block in a memory heap. Each bitmap entry contains a multi-bit value that represents an allocation state of the corresponding memory block. The memory manager manages allocation, deallocation, and reallocation of the memory blocks, and tracks the changes in allocation state via the hierarchical bitmap. Using a-two-bit value, the bitmap can represent at most four different allocation states of the corresponding memory block, including a “free” state, a “sub-allocated” state in which the corresponding memory block is itself an allocated set of smaller memory blocks, a “continue” state in which the corresponding memory block is allocated and part of, but not last in, a larger allocation of plural blocks, and a “last” state in which the corresponding memory block is allocated and last in an allocation of one or more memory blocks.